Sorting algorithm

0x1. 算法概述

0x11. 算法分类

比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此也被称为非线性时间比较类排序。
非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。

0x12. 算法复杂度

0x13. 相关概念

稳定：如果a原本在b前面，而a=b，排序之后仍然在b的前面。
不稳定：如果a原本在b的前面，而a=b，排序之后a可能会出现在b的后面。
时间复杂度：对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。
空间复杂度：是指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数。

0x14. 稳定类

冒泡排序（Bubble Sort） ——O(n²)
插入排序（Insertion Sort）——O(n²)
归并排序（Merge Sort）——O(nlogn) *需要O(n)额外空间*
基数排序（Radix Sort）——O(n*k) *需要O(n)额外空间*

0x15. 不稳定类

选择排序（Selection Sort）——O(n²)
希尔排序（Shell Sort）——O(nlogn)
堆排序（Heap Sort）——O(nlogn)
快速排序（Quick Sort）——期望时间：O(nlogn)；最坏情况：O(n²) // 随机乱数中最快的已知排序

0x2. 插入排序（Insertion Sort）

插入排序(Insertion-Sort)的算法描述是一种简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序的数据，***在已排序序列中从后往前扫描，找到相应位置并插入***。

0x21. 直接插入排序（Straight Insertion Sort）

1. 算法描述

直接插入排序（Straight Insertion Sort）是一种最简单的排序方法，其基本操作是将一条记录插入到已排好序的有序表中，从而得到一个新的、记录数量增1的有序表。

2. 算法步骤

从第一个元素开始，该元素可认为是已排序；
取出下一个元素，在已经排序的元素序列中从后向前扫描；
如果该元素（已排序）大于新元素，将该元素移动到下一个位置；
重复步骤3，直到找到已排序元素小于或等于新元素的位置；
将新元素插入到该位置后；
重复步骤2~5。

3. 算法实现

void InsertSort(SqList &L){ // 对顺序表L做直接插入排序
    for(i = 2; i <= L.length; ++i){
        if(L.r[i].key < L.r[i-1].key){ // "<"，需将r[i]插入有序表
            L.r[0] = L.r[i]; // 将待插入的记录置入监视哨中
            L.r[i] = L.r[i-1]; // r[i-1]后移
            for(j = i-2; L.r[0].key < L.r[j].key; --j){ // 从后向前寻找插入位置                
            	L.r[j+1] = L.r[j]; // 将元素后移
            }
            L.r[j+1] = L.r[0];// 将r[0]即原r[i]，插入到正确位置
        }
    }
}

4. 算法特点

稳定排序；
适用于链式存储结构，在单链表上无需移动记录，只需修改相应的指针。
更适合初始记录基本有序的情况，当初始记录无需时，n较大时，此算法时间复杂度高。

0x22. 折半插入排序（Binary Insertion Sort）

1. 算法描述

直接插入排序采用顺序查找法查找当前记录在已排好序的序列中的插入位置，此处查找操作可利用“折半查找”来实现，由此进行的插入排序称之为折半插入排序（Binary Insertion Sort）。

2. 算法实现

void BInsertSort(SqList &L){ // 对顺序表L做折半插入排序
    for(i = 2; i <= L.length; ++i){
        L.r[0] = L.r[i]; // 将待插入的记录暂存到监视哨中
        low = 1;
        high = i-1; // 初始化
        while(low <= high){ // 在r[low..high]中折半查找插入的位置
            mid = (low + high)/2; // 折半
            if(L.r[mid].key < L.r[high].key){ // 插入点在前一子表
                high = mid - 1;
            }else{// 插入点在后一子表
                low = mid +1;
            }
        }
        for(j = i-1; j >= high+1; --j){ 
            L.r[j+1] = L.r[j]; // 记录后移
        }
        L.r[high + 1] = L.r[0]; //将r[0]即原r[i]，插入到正确位置
    }
}

3. 算法特点

稳定排序；
只能用于顺序结构，不能用于链式存储结构；
适合初始记录无序、n较大时的情况。

0x23. 希尔排序（Shell Sort）

1. 算法描述

希尔排序（Shell Sort）又称“缩小增量排序（Diminishing Increment Sort）”，是插入排序的一种，因D.L.Shell于1959年提出而得名。

直接插入排序，当待排序的记录个数较少且待排序序列的关键字基本有序时，效率较高。希尔排序基于以上两点，从“减少记录个数“和”序列基本有序“两个方面对直接插入排序进行了改进。

2. 算法步骤

先将整个待排序的记录序列分割为若干子序列分别进行直接插入排序，具体算法描述：

选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
按增量序列个数k，对序列进行k趟排序；
每趟排序，根据对应的增量ti，将待排序列分割成若干长度位m的子序列，分别对各子表进行直接插入排序。仅增量因子位1时，整个序列作为一个表来处理，表长度即为整个序列的长度。

3. 算法实现

void ShellInsert(SqList &L,int dk){ // 对顺序表L做一趟增量是dk的希尔插入排序
    for(i = dk + 1; i <= L.length; ++i){
        if(L.r[i].key < L.r[i-dk].key){ // 需将L.r[i]插入有序增量子表
            L.r[0] = L.r[i]; // 暂存在L.r[0]
            for(j = i-dk; j > 0 && L.r[0].key < L.r[j].key; j -= dk){
                L.r[j+dk] = L.r[j]; // 记录后移，直到找到插入位置
            }
            L.r[j+dk] = L.r[0]；// 将r[0]即原r[i]，插入到正确位置
        }
    }
}

void ShellSort(SqList &L,int dt[],int t){ // 按照增量序列dt[0...t-1]对顺序表L做t趟希尔排序
    for(k = 0;k < t; ++k){
        ShellInsert(L,dt[k]);
    }
}

4. 算法特点

记录跳跃式地移动导致排序方法是不稳定的；
只能用于顺序结构，不能用于链式结构；
增量序列可以有各种取法，但应该使增量序列中的值没有除1之外的公因子，并且最后一个增量值必须等于1；
记录总的比较次数和移动次数都比直接插入排序要少，n越大时，效果越明显。所以适合初始记录无序、n较大时的情况。

0x3. 交换排序（Swap Sort）

交换排序的基本思想是：两两比较待排序记录的关键字，一旦发现两个记录不满足次序要求时则进行交换，直到整个序列全部满足要求为止。

0x31.冒泡排序（Bubble Sort）

1. 算法描述

冒泡排序（Bubble Sort）是一种简单的排序算法。它重复地遍历要排序的数列，一次比较两个元素，如果他们的顺序错误就把它们交换过来，遍历数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法名字由来是因为越小的元素回经由交换慢慢”浮“到数列的顶端。

2. 算法步骤

比较相邻的元素，如果第一个比第二个大，就交换它们两个；
对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
针对所有的元素重复以上步骤，除了最后一个；
重复步骤1~3，直到排序完成。

3. 算法实现

void BubbleSort(SqList &L){ // 对顺序表L做冒泡排序
    m = L.length-1;
    flag = 1; // flag标记某一趟排序是否发生交换
    while((m > 0) && (flag == 1)){
        flag = 0; // flag置为0，如果本趟未发生交换，则排序结束
        for(j = 1;j <= m;j++){
            if(L.r[j].key > L.r[j+1].key){
                flag = 1; // flag置为1，表示本趟发生了交换
                t = L.r[j]; // 交换前后两个记录
                L.r[j] = L.r[j+1];
                L.[j+1] = t;
            }
            --m;
        }
    }
}

4. 算法特点

稳定排序；
可用于链式存储结构；
移动记录次数较多，算法平均时间性能比直接插入排序差。当初始记录无序时，n较大时，此算法不适用。

0x32. 快速排序（Quick Sort）

1. 算法描述

快速排序（Quick Sort）是由冒泡排序改进而得的。在冒泡排序过程中，只对相邻的两个记录进行比较，因此每次交换两个相邻记录时只能消除一个逆序。如果能通过两个（不相邻）记录的一次交换，消除多个逆序，则会大大加快排序的速度。快速排序方法中一次交换可能消除多个逆序。

2. 算法步骤

快速排序使用分治法来把一个串（list）分为两个字串（sub-lists）：

从数列中挑出一个元素，称为”基准“（pivot）；
重新排序数列，所有元素比基准值小的摆在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间。这个称为分区（partition）操作；
递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

3. 算法实现

int Partition(SqList &L,int low,int high){// 对顺序表L中的子表r[low...high]进行一遍排序，返回枢纽
    L.r[0] = L.r[row]; // 用子表的第一个记录做枢纽记录
    pivotkey = L.r[low].key; // 枢纽记录关键字保存在pivotkey中
    while(low < high){ // 从表的两端交替地向中间扫描
        while(low < high && L.r[high].key >= pivotkey) --high;
        L.r[low] = L.r[high]; // 将比枢纽记录小的记录移到低端
        while(low < high && L.r[low].key <= pivotkey) ++low;
        L.r[high] = L.r[low]; // 将比枢纽记录大的记录移到高端
    }
    L.r[low] = L.r[0]; // 枢纽记录到位
    return low; // 返回枢纽位置
}

void QSort(SqList &L,int low,int high){
    low = 1;
    high = L.length; //初始化
    if(low < high){ // 长度大于1
        pivotloc = Partition(L,low,high);// 将L.r[low...high]一分为二，pivotloc是枢纽位置
        QSort(L,low,pivotloc-1);// 对左子表递归排序
        Qsort(L,pivotloc+1,high);// 对右子表递归排序
    }
}

void QuickSort(SqList &L){// 对顺序表L做快速排序
    QSort(L,1,L.length);
}

4. 算法特点

记录非顺次的移动导致排序方法是不稳定；
排序过程中需要定位表的下界和上界，所以适合用于顺序结构，很难用于链式结构；
当n较大时，在平均情况下快速排序是所有内部排序方法中速度最快的一种，所以适合初始记录无序、n较大时的情况。

0x4. 选择排序（Selection Sort）

选择排序的基本思想是：每一趟从待排序的记录中选出关键字最小的记录，按顺序放在已排序的记录序列的最后，直到全部排完为止。

0x41. 简单选择排序（SImple Selection Sort）

1. 算法描述

简单选择排序（Simple Selection Sort）也称作直接选择排序。

2. 算法步骤

n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。具体算法描述如下：

初始状态：无序区为R[1..n]，有序区为空；
第i趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R[1..i-1]和R(i..n）。该趟排序从当前无序区中-选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；
n-1趟结束，数组有序化了。

微信图片_20200219183926.jpg

3. 算法实现

void SelectSort(SqList &L){// 对顺序表L做简单选择排序
    for(i = 1; i < L.length; ++i){ // 在L.r[i...L.length]中选择关键字最小的记录
        k = i;
        for(j = i+1;j <= L.length;++j){
            if(L.r[j].key < L.r[k].key) k = j; // k指向此趟排序中关键字最小的记录
        }
        if(k != j){ // 交换r[i]和r[k]
            t = L.r[i];
            L.r[i] = L.r[k];
            L.r[k] = t;
        }
    }
}

4. 算法特点

是一种稳定的排序方法，但图8.6所表现出来的现象是不稳定的，这是因为上述实现选择排序的算法采用”交换记录“的策略所造成的，改变这个策略，可以写出不产生”不稳定现象“的选择排序算法；
可用于链式存储结构；
移动记录次数较少，当每一记录占用的空间较多时，此方法比直接插入排序快。

0x42.堆排序（Heap Sort）

1. 算法描述

堆排序（Heap Sort）是一种树形选择排序，在排序过程中，将待排序的记录r[1…n]看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系，在当前无序的序列中选择关键字最大（或最小）的记录。

2. 算法步骤

将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；
将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]；
由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。

3. 算法实现

// 筛选法调整堆
void HeadAdjust(SqList &L,int s,int m){// 假设r[s+1...m]已经是堆，将其调整为以r[s]为根的大根堆
    rc = L.r[s];
    for(j = 2 * s;j <= m;j *= 2){ // 沿key较大的汉字结点向下筛选
        if(j < m && L.r[j].key < L.r[i+1].key) ++j; // j为key较大的记录的下标
        if(rc.key >= L.r[j].key) break; // rc应插入在位置s上
        L.r[s] = L.r[j];
        s = j;
    }
    L.r[s] = rc;
}

// 堆排序
void HeapSort(SqList &L){
    CreateHeap(L); // 将无序序列L.r[1...L.length]建成大根堆
    for(i = L.length; i > 1; --i){
        x = L.r[1]; // 将堆顶记录和当前未经排序的子序列L.r[1...i]中最后一个记录互换
        L.r[1] = L.r[i];
        L.r[i] = x;
        HeapAdjust(L,1,i-1); // 将L.r[1...i-1]重新调整为大根堆
    }
}

4. 算法特点

是不稳定排序；
只能用于顺序结构，不能用于链式结构；
初始建堆所需的比较次数较多，因此记录数较少时不宜采用。堆排序在最坏情况下时间复杂度为O(nlog2n)，相对于快速排序最坏情况下的O(n²)而言时一个优点，当记录较多时较为高效。

0x5. 归并排序（Merging Sort）

0x51. 算法描述

归并排序（Merging Sort）就是将两个或两个以上的有序表合并成一个有序表的过程。将两个有序表合并成一个有序表的过程称为2-路归并。

0x52. 算法步骤

把长度为n的输入序列分成两个长度为n/2的子序列；
对这两个子序列分别采用归并排序；
将两个排序好的子序列合并成一个最终的排序序列。

0x53. 算法实现

void MSort(RedType R[],RedType T[],int low.int high){
    // R[low...high]归并排序后放入T[low...high]中
    if(low == high){
        T[low] = R[low];
    }
    else{
        mid = (low+high) / 2; // 将当前序列一分为二，求出分裂点mid
        MSort(R,S,low,mid); // 对子序列R[low...mid]递归归并排序，结果放入S[low...mid]
        MSort(R,S,mid+1,high);// 对子序列R[mid+1...high]递归归并排序，结果放入S[mid+1...high]
        Merge(S,T,low,mid,high);// 将S[low...mid]和S[mid+1...high]归并到T[low...high]
    }
}

void MergeSort(SqList &L){// 对顺序表T做归并排序
    MSort(L.r,L.r,1,L.length);
}

0x54. 算法特点

是稳定排序；
可用于链式结构，且不需要附加存储空间，但递归实现时仍需要开辟相应的递归工作栈。

0x6. 基数排序（Radix Sort）

0x61. 算法描述

前述各类排序方法都是建立在关键字比较的基础上，而分配类排序不需要比较关键字的大小，它是根据关键字中的各位的值，通过对待排序记录进行若干趟“分配”与“收集”来实现排序的，是一种借助于多关键字排序的思想对单关键字排序的方法。基数排序（Radix Sortiong）是典型的分配类排序。

0x62. 算法步骤

取得数组中的最大数，并取得位数；
arr为原始数组，从最低位开始取每个位组成radix数组；
对radix进行计数排序（利用计数排序适用于小范围数的特点）。

微信图片_20200219194806.jpg 微信图片_20200219194822.jpg

0x63. 算法实现

void Distribute(SLCell &r,int i,ArrType &f,ArrType &e){
    // 静态链表L的r域中记录已按(keys[0],...,keys[i-1])有序
    // 本算法按第i个关键字keys[i]建立RADIX个子表，使同一子表中记录的keys[i]相同
    //f[0...RADIX-1]和e[0...RADIX-1]分别指向各子表中第一个和最后一个记录
    for(j = 0;j < RADIX; ++j) f[j] = 0; //各子表初始化为空表
    for(p = r[0].next;p;p = r[p].next){
        j = ord(r[p].keys[i]); // ord将记录中第i个关键字映射到[0..RADIX-1]
        if(!f[j]) f[j] = p;
        else r[e[j]].next = p;
        e[j] = p; // 将P所指的结点插入到第j个子表中
    }
}

void Collect(SLCell &r,int i,ArrType f,ArrType e){
    // 本算法按key[i]自小至大地将f[0..RADIX-1]所指各子表依次链接成一个链表
    // e[0...RADIX-1]为各子表的尾指针
    for(j = 0;!f[j];j = succ(j)); // 找第一个非空子表，succ为求后继函数
    r[0].next = f[j]; // r[0].next指向第一个非空子表中第一个结点
    t = e[j];
    while(j < RADIX){
        for(j = succ(j); j < RADIX-1 && !f[j];j = succ(j)); // 找下一个非空子表
        if(f[j]){ // 链接两个非空子表
            r[t].next = f[j]; 
            t = e[j];
        }      
    }
    r[t].next = 0; // t指向最后一个非空子表的最后一个结点
}

void RadixSort(SLList &L){
    // L是采用静态链表表示的顺序表
    // 对L做基数排序，使得L称为按关键字自小到大的有序静态链表，L.r[0]为头结点
    for(i = 0;i < L.recnum; ++i) L.r[i].next = i + 1; 
    L.r[L.renum].next = 0; // 将L改造为静态链表
    for(i = 0;i < L.keynum; ++i){ // 按最低位优先依次对各关键字进行分配和手机
        Distribute(L.r,i,f,e); // 第i趟分配
        Collect(L.r,i,f,e); // 第
    }
}

0x64. 算法特点

是稳定排序；
可用于链式结构，也可用于顺序结构；
时间复杂度可以突破基于关键字比较一类方法的下界O(nlog2n)，达到O(n)；
基数排序使用条件有严格的要求：需要知道各级关键字的主次关系和各级关键字的取值范围。